package B刷题.贪心;

import java.util.PriorityQueue;

/**
 * @author wei.zhao
 * @description: 剑指 Offer 41.数据流中的中位数
 * @date 2022年11月22日 14:34
 */
public class Code02_MedianFinder {

    PriorityQueue<Integer> maxQueue;

    PriorityQueue<Integer> minQueue;

    /**
     * initialize your data structure here.
     */
    public Code02_MedianFinder() {
        maxQueue = new PriorityQueue<>((a, b) -> b - a);
        minQueue = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (maxQueue.isEmpty() || num <= maxQueue.peek()) {
            maxQueue.add(num);
        } else {
            minQueue.add(num);
        }
        while (maxQueue.size() - minQueue.size() > 1) {
            minQueue.add(maxQueue.poll());
        }
        while (minQueue.size() - maxQueue.size() > 1) {
            maxQueue.add(minQueue.poll());
        }
    }

    public double findMedian() {
        if (maxQueue.size() > minQueue.size()) {
            return maxQueue.peek();
        } else if (maxQueue.size() < minQueue.size()) {
            return minQueue.peek();
        } else {
            return ((double) maxQueue.peek() + (double) minQueue.peek()) / 2;
        }
    }

}
